Discovering clusters from a dataset with different shapes, density, andscales is a known challenging problem in data clustering. In this paper, wepropose the RElative COre MErge (RECOME) clustering algorithm. The core ofRECOME is a novel density measure, i.e., Relative $K$ nearest Neighbor KernelDensity (RNKD). RECOME identifies core objects with unit RNKD, and partitionsnon-core objects into atom clusters by successively following higher-densityneighbor relations toward core objects. Core objects and their correspondingatom clusters are then merged through $\alpha$-reachable paths on a KNN graph.Furthermore, we discover that the number of clusters computed by RECOME is astep function of the $\alpha$ parameter with jump discontinuity on a smallcollection of values. A jump discontinuity discovery (JDD) method is proposedusing a variant of the Dijkstra's algorithm. RECOME is evaluated on threesynthetic datasets and six real datasets. Experimental results indicate thatRECOME is able to discover clusters with different shapes, density and scales.It achieves better clustering results than established density-based clusteringmethods on real datasets. Moreover, JDD is shown to be effective to extract thejump discontinuity set of parameter $\alpha$ for all tested dataset, which canease the task of data exploration and parameter tuning.
展开▼
